package com.vint.lintcode;

import com.vint.common.ListNode;

 /**
 * 数位相加，链表， 315,592= 907, 中等
 */
public class Lintcode221 {
	public ListNode addLists2(ListNode l1, ListNode l2) {
		// write your code here
		ListNode head1 = reverse(l1);
		ListNode head2 = reverse(l2);
		ListNode head = addLists(head1, head2);
		return reverse(head);

	}
	public ListNode addLists(ListNode l1, ListNode l2) {
		if (null == l1) {
			return l2;
		}
		if (null == l2) {
			return l1;
		}

		ListNode head = l1;
		int a = l1.val;
		head.val = (a + l2.val) % 10;
		int carry  = (a + l2.val) / 10;
		ListNode headA = l1.next;
		ListNode preA = l1;
		ListNode headB = l2.next;
		ListNode preB = l2;
		while (null != headA && null != headB) {
			preA = headA;
			preB = headB;
			int t = preA.val;
			preA.val = (t + preB.val + carry )%10;
			carry = (t + preB.val + carry ) / 10;
			headA = headA.next;
			headB = headB.next;
		}
		if (null == headA) {
			preA.next = headB;
			while (null != headB) {
				preA = headB;
				int t = preA.val;
				preA.val = (preA.val + carry) % 10;
				carry = (t + carry) / 10;
				headB = headB.next;
			}
		} else {
			while (null != headA) {
				preA = headA;
				int t = preA.val;
				preA.val = (preA.val + carry) % 10;
				carry = (t + carry) / 10;
				headA = headA.next;
			}
		}
		if(carry !=0){
			preA.next = new ListNode(carry);
		}

		return head;

	}
	public ListNode reverse(ListNode head) {
		if (null == head || null == head.next) {
			return head;
		}
		ListNode newHead = head;
		ListNode walk = head.next;
		newHead.next = null;
		while (null != walk) {
			ListNode nextWalk = walk.next;
			walk.next = newHead;
			newHead = walk;
			walk = nextWalk;
		}
		return newHead;
	}
}
